package com.sheng.leetcode.year2023.month04.day27;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2023/04/27
 * <p>
 * 1048. 最长字符串链<p>
 * <p>
 * 给出一个单词数组 words ，其中每个单词都由小写英文字母组成。<p>
 * 如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，<p>
 * 那么我们认为 wordA 是 wordB 的 前身 。<p>
 * 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身<p>
 * 词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，<p>
 * 其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。<p>
 * 从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：words = ["a","b","ba","bca","bda","bdca"]<p>
 * 输出：4<p>
 * 解释：最长单词链之一为 ["a","ba","bda","bdca"]<p>
 * <p>
 * 示例 2:<p>
 * 输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]<p>
 * 输出：5<p>
 * 解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].<p>
 * <p>
 * 示例 3:<p>
 * 输入：words = ["abcd","dbqca"]<p>
 * 输出：1<p>
 * 解释：字链["abcd"]是最长的字链之一。<p>
 * ["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。<p>
 * <p>
 * 提示：<p>
 * 1 <= words.length <= 1000<p>
 * 1 <= words[i].length <= 16<p>
 * words[i] 仅由小写英文字母组成。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/longest-string-chain">1048. 最长字符串链</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1048 {

    @Test
    public void test01() {
//        String[] words = {"a", "b", "ba", "bca", "bda", "bdca"};
        String[] words = {"xbc", "pcxbcf", "xb", "cxbc", "pcxbc"};
//        String[] words = {"abcd", "dbqca"};
        System.out.println(new Solution().longestStrChain(words));
    }
}

class Solution {

    int[] nums;

    String[] text;

    int max = 0, length;

    public int longestStrChain(String[] words) {
        // 根据长度对字符串数组进行从短到长的排序
        Arrays.sort(words, Comparator.comparingInt(String::length));

        // 新思路：对于每个字符串 A，将其当做字符串链的最后一个字符串，计算出它所有的前身字符串 B
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            int x = 0;
            for (int i = 0; i < word.length(); i++) {
                String str = word.substring(0, i) + word.substring(i + 1);
                x = Math.max(x, map.getOrDefault(str, 0) + 1);
            }
            map.put(word, x);
            max = Math.max(max, x);
        }

        // 超时
        // 思路：首先获取 words 中的单词 A，然后找到 单词 A 是前身的其余单词 B，进行 DFS
        length = words.length;
        nums = new int[length];
        text = words;
        int n = 0;
        for (int i = 0; i < length; i++) {
            // 选取 words[i] 作为前身，查询其后身单词
            nums[i] = -1;
            max = Math.max(max, n + 1);
            dfs(i, n + 1);
            nums[i] = 0;
        }
        return max;
    }

    public void dfs(int x, int n) {
        for (int i = x + 1; i < length; i++) {
            if (nums[i] != -1 && chain(text[x], text[i])) {
                nums[i] = -1;
                max = Math.max(max, n + 1);
                dfs(i, n + 1);
                nums[i] = 0;
            }
        }
    }

    public boolean chain(String s1, String s2) {
        // 判断字符串 s1 是不是字符串 s2 的前身，满足则返回 true
        if (s1.length() + 1 == s2.length()) {
            int i = 0, j = 0;
            while (i < s1.length() && j < s2.length()) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    i++;
                    j++;
                } else {
                    j++;
                }
            }
            return j - i <= 1;
        } else {
            return false;
        }
    }
}
